/*
https://leetcode-cn.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/solution/bao-zheng-tu-ke-wan-quan-bian-li-by-leet-mtrw/
 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution1579 {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        int[] b=new int[n+1];
        for (int i=1;i<=n;i++){
            b[i]=i;
        }
        int ans=0;
        for (int[] edge : edges) {
            if (edge[0]==3){
                int dx=find(b,edge[1]);
                int dy=find(b,edge[2]);
                if (dx!=dy){
                    b[dx]=dy;
                    ans++;
                }
            }
        }
        int[] b1=Arrays.copyOf(b,n+1);
        int[] b2=Arrays.copyOf(b,n+1);
        for (int[] edge : edges) {
            if (edge[0]==1){
                int dx=find(b1,edge[1]);
                int dy=find(b1,edge[2]);
                if (dx!=dy){
                    b1[dx]=dy;
                    ans++;
                }
            }else if (edge[0]==2){
                int dx=find(b2,edge[1]);
                int dy=find(b2,edge[2]);
                if (dx!=dy){
                    b2[dx]=dy;
                    ans++;
                }
            }
        }
        int t1=find(b1,1);
        for (int i=2;i<=n;i++){
            if (find(b1,i)!=t1){
                return -1;
            }
        }
        int t2=find(b2,1);
        for (int i=2;i<=n;i++){
            if (find(b2,i)!=t2){
                return -1;
            }
        }
        return edges.length-ans;
    }

    private int find(int[] b, int i) {
        List<Integer> list=new ArrayList<>();
        while (b[i]!=i){
            list.add(i);
            i=b[i];
        }
        for (Integer integer : list) {
            b[integer]=i;
        }
        return i;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1579().maxNumEdgesToRemove(4,new int[][]{{3,1,2},{3,2,3},{1,1,3},{1,2,4},{1,1,2},{2,3,4}}));
    }
}
